#include "trie.h"

Trie::TrieNode::TrieNode():isEndOfWord{false} {}

Trie::Trie(){
    root=new TrieNode();
}

void Trie::insert(const std::string &word){
    TrieNode* node=root;
    for(char ch:word){
        if(node->child.find(ch)==node->child.end())
            node->child[ch]=new TrieNode();
        node=node->child[ch];
    }
    node->isEndOfWord=true;
}

void Trie::searchWithPrefix(TrieNode *node,const std::string &prefix,std::vector<std::string> &results){
    if(node->isEndOfWord)
        results.push_back(prefix);
    for(auto &[ch,childNode]:node->child)
        searchWithPrefix(childNode,prefix+ch,results);
}

std::vector<std::string> Trie::getWordWithPrefix(const std::string &prefix){
    std::vector<std::string> results;
    TrieNode* node=root;
    for(char ch:prefix){
        if(node->child.find(ch)==node->child.end())
            return results;
        node=node->child[ch];
    }
    searchWithPrefix(node,prefix,results);
    return results;
}
